#pragma once 

#include<iostream>

using namespace std;

template<class K>
struct BSTNode{

  BSTNode(const K& key = K())
  :_pleft(nullptr),
  _pright(nullptr),
  _key(key)
  {}

  BSTNode<K> *_pleft;
  BSTNode<K> *_pright;
  K _key;
};

////////////////////////////////

template<class K>
class BinarySearchTree{
  typedef BSTNode<K> Node;
  public:

  /*
   * 默认成员函数
   */ 


  //--------------------------------
  
  //构造函数
  
  BinarySearchTree()=default;
          /*强制生成默认构造函数*/

  //--------------------------------

  //拷贝构造

  BinarySearchTree(const BinarySearchTree<K> &node){
     _proot =  _CopyNode(node._proot);
  }


  //--------------------------------
  
  //赋值重载操作符
  
  BinarySearchTree<K>& operator=( BinarySearchTree<K> node){
    swap(_proot,node._proot);
    return *this;

  }

  
  //--------------------------------

  //析构函数 - 使用递归方法 后序遍历进行Destory
    
  ~BinarySearchTree(){
    _Destroy(_proot);
  }

  //--------------------------------
  bool Insert(const K& key){
    if(_proot == nullptr){//如果root节点为空说明为空树，空树进行第一次插入
      _proot = new Node(key);
      return true;//插入成功进行返回
    }

    Node* cur = _proot;
    Node* tmp;

    while(cur!=nullptr){
      tmp = cur;
      if(key>cur->_key){
        tmp = cur;
        cur = cur->_pright;
      }
      else if(key<cur->_key){
        tmp = cur;
        cur = cur->_pleft;
      }
      else{
        //相同 返回false
          return false;
      }
  }
    if(key>tmp->_key){//链接在右边
      cur = new Node(key);
      tmp->_pright = cur;
    }
    else{//链接在左边
      cur = new Node(key);
      tmp->_pleft = cur;
    }
   return true;
  }
 
  //-----------------------

  void InOrder(){
    /*
     * 自定义类型成员函数若是需要进行递归时
     * 尽量设置一个子函数来方便递归并使用原成员函数进行调用
     * 
     * 在该自定义类型当中，由于传的参数为private私有成员变量
     * 私有成员变量不方便直接进行传参，所以为了方便传参_proot
     * 在private访问限定符的域当中设置一个子函数用来递归
     * 通过原函数去调用这个私有成员函数
     */
   _InOrder(_proot);
   cout<<endl;
  }


  //-----------------------

  bool Find(const K& key){
    Node*pcur = _proot;
    while(pcur){
      if(key>pcur->_key)  pcur = pcur->_pright;
      
      else if(key<pcur->_key) pcur = pcur->_pleft;
      
      else return true;
    }
    return false;
  }



  //-----------------------
  
  bool Erase(const K& key){

    if(nullptr == _proot) return false;
    //找到这个key值
    Node* pcur = _proot;
    Node* parent = _proot;
    while(pcur){
      //进行遍历找到对应的key值
      if(key>pcur->_key){
        parent = pcur;
        pcur = pcur->_pright;
      }
      else if(key<pcur->_key){
        parent = pcur;
        pcur = pcur->_pleft;
      }
      else{
        //已经找到了对应的key值,需要进行删除
         
        
        //左为空的情况
        if(pcur->_pleft == nullptr){
         
          if(pcur == _proot){
              _proot = pcur->_pright;
              delete pcur;
              return true;
          }
          
            if(parent->_pleft == pcur){
            parent->_pleft = pcur->_pright;
          }
          else{
            parent->_pright = pcur->_pright;
          }
          delete pcur;
          return true;
        }

          //右为空的情况
        else if(pcur->_pright == nullptr){

          //判断极端情况(左为空或者右为空的情况下所删节点为根)
          if(pcur == _proot){
              _proot = pcur->_pleft;
              delete pcur;
              return true;
          }

          if(parent->_pleft == pcur){
            parent->_pleft = pcur->_pleft;
          }
          else {
            parent->_pright = pcur->_pleft;
          }
          delete pcur;
          return true;
        }

         //左右都不为空
        else{
           /*
            * 找到左子树的最右子树或右子树的最左子树
            */

            Node*tmp = pcur->_pright; //右子树的最左子树(最小值)
            Node*tmp_parent = pcur;
            while(tmp->_pleft){
              tmp_parent = tmp;
              tmp = tmp->_pleft;    
            }

            /*
             * 找到符合条件的值,进行伪删除法;
             */
            pcur->_key = tmp->_key;
              //说明该子树存在孩子,需要对该子树进行托孤
              //由于所找的数据为该节点右子树的最小值,说明找到的这个最小值不存在左子树,只需要对右子树进行托孤;
              if(tmp_parent->_pleft == tmp){
                tmp_parent->_pleft = tmp->_pright;
                delete tmp;
              }
              else{
                tmp_parent->_pright = tmp->_pright;
                delete tmp;
              }
            return true;
        }

      }
    }
    //未找到key值,pcur指针已经为空,返回false;
    return false;

  }


  //-----------------------


  

  bool FindR(const K& key){
    return _FindR(key,_proot);
  }

  //-----------------------
  
//  bool InsertR(const K&key){
//    if(_proot == nullptr){
//      _proot = new Node(key);
//      return true;
//    }
//
//      if(key>_proot->_key) return _InsertR(key,_proot->_pright,_proot,2);
//      else if(key>_proot->_key) return _InsertR(key,_proot->_pleft,_proot,1);
//      else return false;
//  }
//
// 繁琐且报错(未完成)


  bool InsertR(const K&key){
    return _InsertR(key,_proot);
  }

  //-----------------------
  
  bool EraseR(const K&key){
    return _EraseR(key,_proot);
  }
  
  //-----------------------
  
  private:
  /*
   * 私有成员包括成员函数以及成员变量
   */


   Node *_proot = nullptr; 

  //-----------------------

  protected:


  void _InOrder(Node *root){
    if(root == nullptr){
      return;
    }
  
    _InOrder(root->_pleft);
    cout<<root->_key<<" ";
    _InOrder(root->_pright);
  }
  //-----------------------
    bool _FindR(const K&key,Node*root){
      if(root == nullptr) return false;
      
      if(root->_key == key) return true;

      if(root->_key>key) return _FindR(key,root->_pleft);
      else  return _FindR(key,root->_pright);
    
    
    }  
  //-----------------------
  

//    bool _InsertR(const K&key,Node*root,Node*parent,int flag){
//
//      if(key == root->_key) return false;
//      
//      if(root == nullptr){
//        if(flag == 1) {//左
//          parent->_pleft = new Node(key);
//        } 
//
//        if(flag == 2){//右
//          parent->_pright = new Node(key);
//        }
//        return true;
//
//      }
//
//      if(key > root->_key) return _InsertR(key,root->_pright,root,2);
//      else return _InsertR(key,root->_pleft,root,1);
//    }
//    繁琐且报错


    bool _InsertR(const K&key,Node*& root){
      //纯高效法
      /*
       * 该方法重点在于使用了一个引用来引用指针,
       * 指针既可以为判断条件(为nullptr),
       * 也不缺乏其为上一个节点的左\右子树;
       * */
      if(root == nullptr) {
        root = new Node(key);
        return true;
      }

      if(root->_key < key){
        return _InsertR(key,root->_pright);
      }

      else if(root->_key>key){
        return _InsertR(key,root->_pleft);
      
      }


      else return false;

    }
		//-----------------------

		bool _EraseR(const K& key, Node*& root){

			if(root == nullptr) return false;

			if(key>root->_key) return _EraseR(key,root->_pright);
			else if(key<root->_key) return _EraseR(key,root->_pleft);
			else{
        /*
         * 在该递归删除中同样利用到了指针引用的方式 // 具体能够指针引用是因为递归每次都会开辟出新的栈帧
         * 解决了大部分的判断问题(具体表现在左为空或右为空)
         * 在判断两个子树都不为空的条件下,具体的思路是利用了循环找到可以进行伪删除法的数,再重新调用该子函数完成删除
         *  其想法可以理解为将问题划分为子问题
         *  (将左右均不为空的方式在进行一系列操作后将其最终以左为空或者右为空的问题进行解决);
         * */
        
        Node *cur = root;
          //左为空
        if(root->_pleft == nullptr){
          root = root->_pright;
          delete cur;
          return true;
        } 
        
          //右为空 
        else if(root->_pright == nullptr){
          root = root->_pleft;
          delete cur;
          return true;
        }

          //左右都不为空
        else{
         cur = root->_pleft; 
         while(cur->_pright) cur = cur->_pright;
         root->_key = cur->_key;
         _EraseR(cur->_key,root->_pleft);
         return true; 
        }  


			}
		}

		//-----------------------

    Node* _CopyNode(const Node* node){
      
      if(node == nullptr) {
        return nullptr;
      }
      Node*newnode = new Node(node->_key);
      newnode->_pleft = _CopyNode(node->_pleft);
      newnode->_pright = _CopyNode(node->_pright);
      return newnode;
    }

    //------------------------
    
    void _Destroy(Node*& root){
      if(root == nullptr) return;
      _Destroy(root->_pleft);
      _Destroy(root->_pright);
      delete root;
      root = nullptr;
    }

};

